package arithmetic_40;

import java.util.List;

/**
 *
 * @author wxh
 */
public class Solution_7 {

	public int lengthOfLIS(int[] nums) {

		if (nums == null || nums.length == 0) {
			return 0;
		}

		int res = 1;
		// 下标i表示（状态定义）：从下标0开始，到i元素的最长子序列的长度
		int[] dp = new int[nums.length + 1];

		// 初始化dp最长子序列，因为至少最长上升子序列是1，比如 [5,4,3,2,1]
		for (int i = 0; i < nums.length; i++) {
			dp[i] = 1;
		}

		for (int i = 1; i < nums.length; i++) { // 从dp[1]开始递推（因为至少最长上升子序列是1）
			for (int j = 0; j < i; j++) { // 看i前面已经递推出来的状态
				if (nums[j] < nums[i]) { // 如果前面的元素小于i，说明dp[i]可以利用前面dp[j]的结果，组成最长子序列
					dp[i] = Math.max(dp[i], dp[j] + 1); // 用当前dp[j]+1的结果，和之前已经计算过的dp[i]做比较，取较大值，更新dp[i]
				}
			}

			// 全局更新res
			res = Math.max(res, dp[i]);
		}
		return res;
	}

}